package com.dsx.myblog;

public class QuickSort {

    static int[] arr = {4,4,4,4,4,4,4,4,4};

    public static void main(String[] args) {
        QuickSort quickSort = new QuickSort();
        quickSort.quickSort(arr,0,arr.length-1);
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }


    public void quickSort(int[] arr, int start, int end){

        if(end - start <= 0){
            return;
        } else if(end-start == 1){
            if(arr[start] > arr[end]){
                swap(arr, start, end);
            }
        } else {
            int base = medial3(arr, start, end);
            int left = start;
            int right = end -1;
            while (true){
                while (arr[left++] < base){}
                while (arr[right--] > base){}
                if(left-1 < right+1){
                    swap(arr, left-1, right+1);
                } else {
                    break;
                }
            }
            swap(arr, left-1, end);

            quickSort(arr, start, left-1);
            quickSort(arr, left, end);
    }



}







    public void swap(int[] arr, int start, int end){
        arr[start] = arr[start] ^ arr[end];
        arr[end]   = arr[start] ^ arr[end];
        arr[start] = arr[start] ^ arr[end];
    }


    public int medial3(int[] arr, int start, int end){
        int left = arr[start];
        int center = arr[(end+start)/2];
        int right = arr[end];
        int index;


        if(left > center){
            if(center < right){
                index = right > left ? start : end;
            } else {
                index = (end+start)/2;
            }
        } else{
            if(right < center){
                index =left > right ? end : start;
            } else{
                index = (end+start)/2;
            }
        }
        swap(arr,index,end);
        return arr[end];
    }


}
